import com.cjm.algorithm.ListNode;
import com.cjm.algorithm.TreeNode;

import java.util.*;

public class Demo1 {

    public static void main(String[] args) {
        Demo1 demo1 = new Demo1();
        System.err.println(demo1.compress(new char[]{'a', 'b', 'b', 'b', 'b', 'b', 'b', 'b', 'b', 'b', 'b', 'b', 'b'}));
    }

    public List<List<Integer>> threeSum(int[] nums) {
        return new ArrayList<>();
    }

    public int minSubArrayLen(int s, int[] nums) {
        int lo = 0, hi = 0, sum = 0, min = Integer.MAX_VALUE;
        while (hi < nums.length) {
            sum += nums[hi++];
            while (sum >= s) {
                min = Math.min(min, hi - lo);
                sum -= nums[lo++];
            }
        }
        return min == Integer.MAX_VALUE ? 0:min;
    }

    int res = Integer.MAX_VALUE;
    public int coinChange1(int[] coins, int amount){
        if(amount==0){
            return 0;
        }
        Arrays.sort(coins);
        mincoin(coins,amount,coins.length-1,0);
        return res==Integer.MAX_VALUE? -1:res;
    }
    private void mincoin(int[] coins,int amount, int index, int count){
        if(amount==0){
            res = Math.min(res,count);
            return;
        }
        if(index<0){
            return;
        }
        for(int i = amount/coins[index];i>=0 && i+count<res; i--){
            mincoin(coins,amount - (i*coins[index]), index-1, count+i);
        }
    }

    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int j = 0; j < coins.length; j++) {
                if (i>=coins[j] && dp[i - coins[j]] != Integer.MAX_VALUE) {
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
    }

    public List<List<Integer>> permuteUnique(int[] nums) {
        List<Integer> container = new ArrayList<>();
        List<List<Integer>> res = new ArrayList<>();
        boolean[] used = new boolean[nums.length];
        Arrays.sort(nums);
        xx1(nums, container, res, used);
        return res;
    }

    private void xx1(int[] nums, List<Integer> container, List<List<Integer>> res, boolean[] used) {
        if (container.size() == nums.length) {
            res.add(new ArrayList<>(container));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            int cur = nums[i];
            if (used[i]) {
                continue;
            }
            if (i > 0 && cur == nums[i - 1] && !used[i - 1]) {
                continue;
            }
            container.add(nums[i]);
            used[i] = true;
            xx1(nums, container, res, used);
            used[i] = false;
            container.remove(container.size() - 1);
        }
    }

    public List<List<Integer>> permute(int[] nums) {
        List<Integer> container = new ArrayList<>();
        List<List<Integer>> res = new ArrayList<>();
        boolean[] used = new boolean[nums.length];
        xx(nums, container, res, used);
        return res;
    }

    public void xx(int[] nums, List<Integer> container, List<List<Integer>> res, boolean[] used) {
        if (container.size() == nums.length) {
            res.add(new ArrayList<>(container));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) {
                continue;
            }
            container.add(nums[i]);
            used[i] = true;
            xx(nums, container, res, used);
            used[i] = false;
            container.remove(container.size() - 1);
        }
    }

    public String longestCommonPrefix(String[] strs) {
        if (strs.length == 0) {
            return "";
        }
        String ans = strs[0];
        for (int i = 1; i < strs.length; i++) {
            int j = 0;
            for (; j < ans.length() && j < strs[i].length(); j++) {
                if (ans.charAt(j) != strs[i].charAt(j)) {
                    break;
                }
            }
            ans = ans.substring(0, j);
            if ("".equals(ans)) {
                return "";
            }
        }
        return ans;
    }

    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> count = new HashMap<>();
        int max = 0;
        int left = 0;
        for (int i = 0; i < s.toCharArray().length; i++) {
            char c = s.charAt(i);
            count.put(c, count.getOrDefault(c, 0) + 1);
            while (count.get(c) > 1) {
                count.put(s.charAt(left), count.get(s.charAt(left)) - 1);
                left++;
            }
            max = Math.max(max, i - left);
        }
        return max;
    }

    public int compress1(char[] chars) {
        int left = 0, size = 0;
        for (int right = 0; right <= chars.length; right++) {
            if (right == chars.length || chars[right] != chars[left]) {
                chars[size++] = chars[left];
                if (right - left > 1) {
                    for (char c : String.valueOf(right - left).toCharArray()) {
                        chars[size++] = c;
                    }
                }
                left = right;
            }
        }
        return size;
    }

    public int compress(char[] chars) {
        if (chars == null || chars.length == 0) {
            return 0;
        }
        Character last = null;
        int count = 0;
        StringBuilder sb = new StringBuilder();
        for (char c : chars) {
            if (last == null) {
                last = c;
                count = 1;
                continue;
            }
            if (c == last) {
                count++;
            } else {
                if (count == 1) {
                    sb.append(last);
                } else {
                    sb.append(last).append(count);
                }
                last = c;
                count = 1;
            }
        }
        String string;
        if (count == 1) {
            string = sb.append(last).toString();
        } else {
            string = sb.append(last).append(count).toString();
        }

        for (int i = 0; i < string.length(); i++) {
            chars[i] = string.charAt(i);
        }

        return string.length();
    }

    public String compressString(String S) {
        Character last = null;
        int count = 0;
        StringBuilder sb = new StringBuilder();
        for (char c : S.toCharArray()) {
            if (last == null) {
                last = c;
                count = 1;
                continue;
            }
            if (c == last) {
                count++;
            } else {
                sb.append(last).append(count);
                last = c;
                count = 1;
            }
        }

        String string = sb.append(last).append(count).toString();
        if (string.length() > S.length()) {
            return S;
        }
        return string;
    }


    ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        ListNode dummy = new ListNode(-1);
        ListNode p = dummy;
        PriorityQueue<ListNode> pq = new PriorityQueue<ListNode>(lists.length, new Comparator<ListNode>() {

            @Override
            public int compare(ListNode o1, ListNode o2) {
                return o1.val - o2.val;
            }
        });

        // 把这些链表节点都放入到堆中去
        for (ListNode node : lists) {
            if (node != null) {
                pq.add(node);
            }
        }

        while (!pq.isEmpty()) {
            // 从堆中拿出最小的
            ListNode little = pq.poll();
            p.next = little;
            if (little.next != null) {
                pq.add(little.next);
            }
            p = p.next;
        }
        return dummy.next;
    }

    ListNode partition(ListNode head, int x) {
        // 小于的
        ListNode dummy1 = new ListNode(-1);
        // 大于的
        ListNode dummy2 = new ListNode(-1);

        ListNode p1 = dummy1, p2 = dummy2;
        ListNode p = head;
        while (p != null) {
            // 这里前进的都是p1， p2
            if (p.val >= x) {
                p2.next = p;
                p2 = p2.next;
            } else {
                p1.next = p;
                p1 = p1.next;
            }

            // 断开之前的链接
            ListNode temp = p.next;
            p.next = null;
            p = temp;
        }

        p1.next = dummy2.next;
        return dummy1.next;
    }

    ListNode mergeTwoList(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-1), p = dummy;
        ListNode p1 = l1, p2 = l2;
        while (p1 != null && p2 != null) {
            // 比较p1和p2两个指针
            // 将值较小的节点接到p指针
            if (p1.val > p2.val) {
                p.next = p2;
                p2 = p2.next;
            } else {
                p.next = p1;
                p1 = p1.next;
            }
            p = p.next;
        }

        if (p1 != null) {
            p.next = p1;
        }

        if (p2 != null) {
            p.next = p2;
        }

        return dummy.next;
    }

    /**
     * 二叉搜索树的最近公共祖先
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root.val > p.val && root.val > q.val) {
            // 根节点， 大于左节点， 大于右节点
            return lowestCommonAncestor(root.left, p, q);
        } else if (root.val < p.val && root.val < q.val) {
            // 根节点， 小于左节点， 小于右节点
            return lowestCommonAncestor(root.right, p, q);
        } else {
            // 根节点
            return root;
        }
    }

    /**
     * 搜索
     */
    public TreeNode searchBST(TreeNode root, int target) {
        return findTarget700(root, target);
    }

    private TreeNode findTarget700(TreeNode root, int target) {
        if (root == null) return null;
        if (root.val == target) {
            return root;
        }
        TreeNode left = findTarget700(root.left, target);
        if (left != null) {
            return left;
        }
        return findTarget700(root.right, target);
    }

    /**
     * 是否对称
     */
    public boolean isSymmetric(TreeNode root) {
        return isMirror(root, root);
    }

    public boolean isMirror(TreeNode left, TreeNode right) {
        if (left == null && right == null) return true;
        if (left == null || right == null) return false;
        return (left.val == right.val) && isMirror(left.right, right.left) && isMirror(left.left, right.right);
    }

    /**
     * 这个东西， 这个是从下而上的，这一层是否已经超过了定义？
     * 如果已经超过了定义， 那么这个就已经不是平衡树了
     * 如果是， 那么它的深度再加上本层的1
     */
    public boolean isBalanced(TreeNode root) {
        return recur(root) != -1;
    }

    private int recur(TreeNode root) {
        if (root == null) return 0;
        int left = recur(root.left);
        if (left == -1) return -1;
        int right = recur(root.right);
        if (right == -1) return -1;
        // 其实，这里就是从下往上增加呗
        return Math.abs(left - right) < 2 ? Math.max(left, right) + 1 : -1;
    }


    /**
     * 最大深度
     */
    int maxDep = Integer.MAX_VALUE;

    public int minDepth1(TreeNode root) {
        maxDep = Integer.MAX_VALUE;
        if (root == null) return 0;
        methodxx(root, 1);
        return maxDep;
    }

    private void methodxx(TreeNode root, int depth) {
        if (root.left == null && root.right == null) {
            maxDep = Math.min(maxDep, depth);
            return;
        }
        if (root.left != null) methodxx(root.left, depth + 1);
        if (root.right != null) methodxx(root.right, depth + 1);
    }

    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int minDepth = 1;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (node.left == null && node.right == null) {
                    return minDepth;
                }
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            minDepth++;
        }
        return minDepth;
    }
}
